﻿#define _CRT_SECURE_NO_WARNINGS 1
// 原题连接：https://www.acwing.com/problem/content/2062/
/*
题目描述：
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。

不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。

牛皮可用一个 N×M
 的字符矩阵来表示，如下所示：

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
其中，X
 表示斑点部分。

如果两个 X
 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。

在上面的例子中，他只需要给三个 .
 区域内涂色即可（新涂色区域用 ∗
 表示）：

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....
请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式
第一行包含两个整数 N
 和 M
。

接下来 N
 行，每行包含一个长度为 M
 的由 X
 和 .
 构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出格式
输出需要涂色区域的最少数量。

数据范围
1≤N,M≤50
输入样例：
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
输出样例：
3
*/

// 开始解题：
// 方法——bfs
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
char grid[55][55];
int vis[55][55];
int n = 0, m = 0;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int INF = 0x3f3f3f3f;
int ret = INF;

bool check(int bx, int by) {
	for (int k = 0; k < 4; k++) {
		int x = bx + dx[k], y = by + dy[k];
		if (x >= 0 && x < n && y >= 0 && y < m) {
			if (grid[x][y] == '.') {
				return true;
			}
		}
	}
	return false;	
}

void bfs(int bx, int by, int number, vector<pair<int, int>>&points) {
	vis[bx][by] = number;
	queue<pair<int, int>> q;
	q.push({ bx, by });
	points.push_back({ bx, by });

	while (!q.empty()) {
		int a = q.front().first, b = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int x = a + dx[k], y = b + dy[k];
			if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && grid[x][y] == 'X') {
				vis[x][y] = number;
				q.push({ x, y });
				if (check(x, y)) {
					points.push_back({ x, y });
				}
			}
		}
	}
}

// 核心思想：正难则反，转化成求一个联通块中的某一个边缘点连接到另一个联通块的某一个边缘点的曼哈顿距离
// 求出其中的最小曼哈顿距离 - 1
int main() {
	memset(vis, 0, sizeof vis);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", grid[i]);
	}
	vector<pair<int, int>> points1, points2;
	// 先将两个连通块标记出来
	int number = 1;
	for (int i = 0; i < n; i++) {
		if (number == 3) {
			break;
		}
		for (int j = 0; j < m; j++) {
			if (number == 3) {
				break;
			}
			if (!vis[i][j] && grid[i][j] == 'X') {
				if (number == 1) {
					bfs(i, j, number++, points1);
				}
				else {
					bfs(i, j, number++, points2);
				}
			}
		}
	}

	for (int i = 0; i < points1.size(); i++) {
		for (int j = 0; j < points2.size(); j++) {
			int x1 = points1[i].first, y1 = points1[i].second;
			int x2 = points2[j].first, y2 = points2[j].second;
			ret = min(ret, abs(x1 - x2) + abs(y1 - y2) - 1);
		}
	}
	cout << ret << endl;
	return 0;
}